package com.hardy.leecode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Author: Hardy
 * Date:   2020/11/3
 * Description:
 * -
 * 1020. 飞地的数量
 * 给出一个二维数组 A，每个单元格为 0（代表海）或 1（代表陆地）。
 * <p>
 * 移动是指在陆地上从一个地方走到另一个地方（朝四个方向之一）或离开网格的边界。
 * <p>
 * 返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。
 * <p>
 * 示例 1：
 * <p>
 * 输入：[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
 * 输出：3
 * 解释：
 * 有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。
 * 示例 2：
 * <p>
 * 输入：[[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
 * 输出：0
 * 解释：
 * 所有 1 都在边界上或可以到达边界。
 * <p>
 * 提示：
 * <p>
 * 1 <= A.length <= 500
 * 1 <= A[i].length <= 500
 * 0 <= A[i][j] <= 1
 * 所有行的大小都相同
 **/
public class Que1020 {

    public static void main(String[] args) {

        //int[][] a = {{0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1}, {1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0}, {0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0}, {1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1}, {0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0}, {1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1}, {0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0}, {0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0}, {1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0}, {1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1}};
        int[][] a = {{0, 0, 0, 0}, {1, 0, 1, 0}, {0, 1, 1, 0}, {0, 0, 0, 0}};

        System.out.println(new Solution().numEnclaves(a));
    }

    static class Solution {

        public int numEnclaves(int[][] a) {
            int maxi = a.length;
            int maxj = a[0].length;

            if (maxi <= 2 && maxj <= 2) return 0;

            for (int i = 0; i < maxi; i++) {
                if (a[i][0] == 1) cover(i, 1, maxi, maxj, a);
                if (a[i][maxj - 1] == 1) cover(i, maxj - 2, maxi, maxj, a);
            }

            for (int j = 0; j < maxj; j++) {
                if (a[0][j] == 1) cover(1, j, maxi, maxj, a);
                if (a[maxi - 1][j] == 1) cover(maxi - 2, j, maxi, maxj, a);
            }

            int c = 0;
            int binj = (maxj + 1) / 2;
            for (int i = 1; i < maxi - 1; i++) {
                for (int j = 1; j < binj; j++) {
                    if (a[i][j] == 1) c++;

                    if (maxj - 1 - j <= j) break;
                    if (a[i][maxj - 1 - j] == 1) c++;
                }
            }
            return c;
        }

        private void cover(int i, int j, int maxi, int maxj, int[][] a) {
            if (a[i][j] == 0) return;

            Queue<Integer> q = new LinkedList<>();
            q.offer(i * 1000 + j);

            while (!q.isEmpty()) {
                for (int x = 0; x < q.size(); x++) {
                    Integer v = q.poll();

                    i = v / 1000;
                    j = v % 1000;

                    a[i][j] = 0;

                    // [i-1][j]
                    if (i - 1 > 0 && a[i - 1][j] == 1) q.offer((i - 1) * 1000 + j);
                    // [i+1][j]
                    if (i + 1 < maxi && a[i + 1][j] == 1) q.offer((i + 1) * 1000 + j);

                    // [i][j-1]
                    if (j - 1 > 0 && a[i][j - 1] == 1) q.offer(i * 1000 + (j - 1));
                    // [i][j+1]
                    if (j + 1 < maxj && a[i][j + 1] == 1) q.offer(i * 1000 + (j + 1));
                }
            }
        }

        private void print(int[][] a) {
            for (int i = 0; i < a.length; i++) {
                for (int j = 0; j < a[0].length; j++) {
                    System.out.print(a[i][j]);
                    System.out.print(" ");
                }
                System.out.println("");
            }
        }
    }
}
